package queue

import (
	"runtime"
	"sync/atomic"
)

/*
 * cas锁 多线程安全
 */

type ringQueueNode struct {
	data interface{}
	flag uint32
}

type RingQueue struct {
	_padding0  [64]byte
	size       uint32
	capMod     uint32
	_padding1  [64]byte
	records    []*ringQueueNode
	_padding2  [64]byte
	readIndex  uint32
	_padding3  [64]byte
	writeIndex uint32
}

func NewRingQueue(capaciity uint32) *RingQueue {
	q := new(RingQueue)
	q.size = RoundUp(capaciity)
	q.capMod = q.size - 1
	q.records = make([]*ringQueueNode, q.size)
	for i := uint32(0); i < q.size; i++ {
		q.records[i] = &ringQueueNode{}
	}
	return q
}

func (m *RingQueue) Write(value interface{}) bool {
	w := atomic.LoadUint32(&m.writeIndex)
	var n *ringQueueNode
	var w1 uint32
	for {
		n = m.records[w]
		if 1 == atomic.LoadUint32(&n.flag) {
			runtime.Gosched()
			w1 = atomic.LoadUint32(&m.writeIndex)
			if w1 == w {
				return false
			}
			w = w1
			runtime.Gosched()
			continue
		}

		if atomic.CompareAndSwapUint32(&m.writeIndex, w, (w+1)&m.capMod) {
			break
		}

		w = atomic.LoadUint32(&m.writeIndex)
		runtime.Gosched()
	}
	n.data = value
	atomic.StoreUint32(&n.flag, 1)
	return true
}

func (m *RingQueue) Read() (interface{}, bool) {
	r := atomic.LoadUint32(&m.readIndex)
	var n *ringQueueNode
	var r1 uint32
	for {
		n = m.records[r]
		if 0 == atomic.LoadUint32(&n.flag) {
			runtime.Gosched()
			r1 = atomic.LoadUint32(&m.readIndex)
			if r1 == r {
				return nil, false
			}
			r = r1
			runtime.Gosched()
			continue
		}

		if atomic.CompareAndSwapUint32(&m.readIndex, r, (r+1)&m.capMod) {
			break
		}

		r = atomic.LoadUint32(&m.readIndex)
		runtime.Gosched()
	}

	data := n.data
	n.data = nil
	atomic.StoreUint32(&n.flag, 0)
	return data, true
}

func (m *RingQueue) Capacity() uint32 {
	return m.size - 1
}

func RoundUp(v uint32) uint32 {
	v--
	v |= v >> 1
	v |= v >> 2
	v |= v >> 4
	v |= v >> 8
	v |= v >> 16
	v++
	return v
}
